#include <iostream>
#include <vector>
#include <unordered_set>

struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}

};

class Solution1 {
public:
    bool hasCycle(ListNode* head) {
        if (!head || !head->next) return false;
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast && slow)
        {
            fast = fast->next;
            if (fast) fast = fast->next;
            slow = slow->next;
            if (fast == slow)
                return true;
        }
        return false;
    }
};

class Solution2 {
public:
    ListNode* detectCycle(ListNode* head) {
        if (!head || !head->next) return nullptr;
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast)
        {
            fast = fast->next;
            if (fast) fast = fast->next;
            slow = slow->next;
            if (fast == slow)
            {
                ListNode* cur = slow;
                ListNode* newp = head;
                while (cur != newp)
                {
                    cur = cur->next;
                    newp = newp->next;
                }
                return cur;
            }
        }
        return nullptr;
    }
};

class Solution3 {
public:
    int climbStairs(int n) {
        vector<int> dp(n);
        dp[0] = 1; dp[1] = 2;
        for (int i = 2; i < n; ++i)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n - 1];
    }
};

class Solution4 {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int p1 = 0; int p2 = numbers.size() - 1;
        while (p1 < p2)
        {
            int sum = numbers[p1] + numbers[p2];
            if (sum < target) ++p1;
            else if (sum > target) --p2;
            else break;
        }
        return { p1 + 1,p2 + 1 };
    }
};

class Solution5 {
public:
    bool canAliceWin(vector<int>& nums) {
        int sum1 = 0; int sum2 = 0;
        for (int num : nums)
        {
            if (num / 10) sum2 += num;
            else sum1 += num;
        }
        return sum1 != sum2;
    }
};

class Solution6 {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* mid = slow->next;
        slow->next = nullptr;
        return mid;
    }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;
        ListNode dummy = ListNode(-1);
        ListNode* tail = &dummy;
        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        if (list1) tail->next = list1;
        if (list2) tail->next = list2;
        return dummy.next;
    }

    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* mid = middleNode(head);

        ListNode* l = sortList(head);
        ListNode* r = sortList(mid);

        return mergeTwoLists(l, r);
    }
};

class Solution7 {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* mid = slow->next;;
        slow->next = nullptr;
        return mid;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode dummy = ListNode(-1);
        while (head)
        {
            ListNode* next = head->next;
            head->next = dummy.next;
            dummy.next = head;
            head = next;
        }
        return dummy.next;
    }

    bool isPalindrome(ListNode* head) {
        if (!head->next) return true;

        ListNode* mid = middleNode(head);
        mid = reverseList(mid);

        while (head && mid)
        {
            if (head->val != mid->val)
                return false;
            head = head->next;
            mid = mid->next;
        }
        return true;
    }
};

class Solution8 {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return {};
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res;
        res.push_back(intervals[0]);
        for (auto& v : intervals)
        {
            if (v[0] <= res.back()[1])
            {
                res.back()[1] = max(res.back()[1], v[1]);
            }
            else
            {
                res.push_back({ v[0],v[1] });
            }
        }
        return res;
    }
};

class Solution9 {
public:
    string removeDuplicateLetters(string s) {
        int cnt[26] = { 0 };
        for (char c : s)
            ++cnt[c - 'a'];
        string res;
        bool inAns[26] = { false };
        for (char c : s)
        {
            --cnt[c - 'a'];
            if (inAns[c - 'a']) continue;
            while (!res.empty() && c < res.back() && cnt[res.back() - 'a'])
            {
                inAns[res.back() - 'a'] = false;
                res.pop_back();
            }
            res.push_back(c);
            inAns[c - 'a'] = true;
        }
        return res;
    }
};

class Solution10 {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next) return head;
        ListNode* p = head;
        int n = 0;
        while (p)
        {
            p = p->next;
            ++n;
        }
        k %= n;
        if (!k) return head;
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev1 = head;
        ListNode* prev2 = head;
        while (k--) fast = fast->next;
        while (fast)
        {
            prev1 = fast;
            fast = fast->next;
            prev2 = slow;
            slow = slow->next;
        }
        prev1->next = head;
        prev2->next = nullptr;
        return slow;
    }
};